package 题目集.线段树or树状数组.线段树;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 有类似的模板：https://www.luogu.com.cn/problem/P1253
 * 对数器验证
 * 存在加法和重置的线段树.
 * 重置操作会覆盖掉之前的加法操作
 */
public class ch03_综合模板_存在优先级 {

    static Node[] tr;
    static long[] src;
    static int n, tn;

    public static void init(long[] arr) {
        n = arr.length - 1;
        src = arr;
        tn = (int) Math.pow(2, Math.ceil(Math.log(n) / Math.log(2)) + 1);
        tr = new Node[tn];
        build(1, 1, n);
    }

    public static void build(int i, int l, int r) {
        tr[i] = new Node(l, r);
        if (l == r) {
            tr[i].val = src[l];
            return;
        }
        int m = l + r >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m + 1, r);
        pull(i);
    }

    public static void add(int i, int l, int r, long v) {
        if (l <= tr[i].l && tr[i].r <= r) {
            addLazy(i, v);
            return;
        }
        push(i);
        int m = tr[i].l + tr[i].r >> 1;
        if (l <= m) {
            add(i << 1, l, r, v);
        }
        if (m < r) {
            add(i << 1 | 1, l, r, v);
        }
        pull(i);
    }

    public static void update(int i, int l, int r, long v) {
        if (l <= tr[i].l && tr[i].r <= r) {
            updateLazy(i, v);
            return;
        }
        push(i);
        int m = tr[i].l + tr[i].r >> 1;
        if (l <= m) {
            update(i << 1, l, r, v);
        }
        if (m < r) {
            update(i << 1 | 1, l, r, v);
        }
        pull(i);
    }

    public static long query(int i, int l, int r) {
        if (l <= tr[i].l && tr[i].r <= r) {
            return tr[i].val;
        }
        push(i);
        int m = tr[i].l + tr[i].r >> 1;
        long res = 0;
        if (l <= m) {
            res += query(i << 1, l, r);
        }
        if (m < r) {
            res += query(i << 1 | 1, l, r);
        }
        return res;
    }

    public static void pull(int i) {
        tr[i].val = tr[i << 1].val + tr[i << 1 | 1].val;
    }

    public static void push(int i) {
        int l = i << 1;
        int r = l | 1;
        //修改
        if (tr[i].tag) {
            updateLazy(l, tr[i].update);
            updateLazy(r, tr[i].update);
            tr[i].tag = false;
        }
        //增加
        if (tr[i].add != 0) {
            addLazy(l, tr[i].add);
            addLazy(r, tr[i].add);
            tr[i].add = 0;
        }
    }

    public static void addLazy(int i, long v) {
        tr[i].val += tr[i].len * v;
        tr[i].add += v;
    }

    public static void updateLazy(int i, long v) {
        tr[i].val = tr[i].len * v;
        tr[i].update = v;
        tr[i].tag = true;
        tr[i].add = 0;
    }

    static class Node {
        int l, r, len;
        long val, add, update;
        boolean tag;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
            len = r - l + 1;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "l=" + l +
                    ", r=" + r +
                    ", len=" + len +
                    ", val=" + val +
                    ", add=" + add +
                    ", update=" + update +
                    ", flag=" + tag +
                    '}';
        }
    }

    @Test
    public void test() {
        long[] arr = {0, 2, 4};  //0位置弃而不用
        init(arr);
        add(1, 1, 2, 3);
        add(1, 1, 2, 4);
//        update(1, 1, 1, 5);
        long query = query(1, 2, 2);
        System.out.println(query);
    }

    static Random random = new Random();

    public static void main(String[] args) {
        int maxN = 10000;
        int maxV = maxN;
        int t = 100;
        int count = 10000;
        System.out.println("测试开始");
        while (count-- > 0) {
            compare(maxN, maxV, t);
        }
        System.out.println("测试结束");
    }

    public static void compare(int maxN, int maxV, int count) {
        int len = random.nextInt(maxN) + 1;

        long[] origin = new long[len + 1];
        for (int i = 1; i <= len; i++) {
            origin[i] = random.nextInt(maxV);
        }
        check = origin.clone();
        init(origin.clone());

        int[][] ops = new int[count][4];

        for (int i = 0; i < count; i++) {
            ops[i][0] = random.nextInt(3);
            ops[i][1] = random.nextInt(len) + 1;
            ops[i][2] = random.nextInt(len) + 1;

            int l = Math.min(ops[i][1], ops[i][2]);
            int r = Math.max(ops[i][1], ops[i][2]);
            int v = random.nextInt(maxV + maxV / 2) - maxV / 2;

            ops[i][1] = l;
            ops[i][2] = r;
            ops[i][3] = v;

            if (ops[i][0] == 0) {
                checkADD(l, r, v);
                add(1, l, r, v);
            } else if (ops[i][0] == 1) {
                checkUpdate(l, r, v);
                update(1, l, r, v);
            } else {
                long ans1 = checkQuery(l, r);
                long ans2 = query(1, l, r);
                if (ans1 != ans2) {
                    System.out.println(i + "：出错了!\t ans=" + ans1 + "\terror=" + ans2);
                    for (int[] op : ops) {
                        System.out.println(Arrays.toString(op));
                    }
                    break;
                }
            }
        }
    }

    static long[] check;

    public static void checkADD(int l, int r, int v) {
        while (l <= r) {
            check[l++] += v;
        }
    }

    public static void checkUpdate(int l, int r, int v) {
        while (l <= r) {
            check[l++] = v;
        }
    }

    public static long checkQuery(int l, int r) {
        long res = 0;
        while (l <= r) {
            res += check[l++];
        }
        return res;
    }
}
